“School of Computer Science”
Back to Papers HomeBack to Papers of School of Computer Science
| Paper IPM / Computer Science / 10991 |
|
||||||
| Abstract: | |||||||
|
In this paper, we use the regular distribution method to design a perfect load balancing algorithm for an n-star with a maximum error of 1 and a time complexity of 3n(n+1). This algorithm is based on the novel notion of leader trees. A second algorithm proposed in this paper as an enhancement to our first algorithm and uses an arbitrary spanning tree as the leader tree and has a worst time complexity of 2.25n 2�3n+0.75. We also discuss the issue of dynamically selecting the leader tree and hybrid load balancing algorithms in general. Furthermore, we present a hybrid algorithm for load balancing on the star interconnection network which benefits from a diffusion load balancing preprocessing phase and shows a smaller mean time complexity than our two first algorithms.
Download TeX format |
|||||||
| back to top | |||||||
